/*
 * 基础模板 - 包含所有常用头文件和工具函数
 * 使用场景: 所有算法题的基础，提供快速IO、常用宏、数学函数等
 * 特点: 开箱即用，无需额外配置
 */

#pragma once
#include <algorithm>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

// 常用类型定义 - 简化代码书写
using ll = long long;           // 长整型，防止溢出
using ull = unsigned long long; // 无符号长整型
using ld = long double;         // 高精度浮点数
using pii = pair<int, int>;     // 整数对，常用于坐标、边等
using pll = pair<ll, ll>;       // 长整型对
using vi = vector<int>;         // 整数向量
using vl = vector<ll>;          // 长整型向量
using vs = vector<string>;      // 字符串向量
using vvi = vector<vi>;         // 二维整数向量，常用于矩阵
using vvl = vector<vl>;         // 二维长整型向量

// 常用常量 - 避免魔法数字
const int INF = 1e9;      // 整数无穷大，用于初始化距离等
const ll LINF = 1e18;     // 长整型无穷大
const int MOD = 1e9 + 7;  // 模数，常用于取模运算
const double EPS = 1e-9;  // 浮点数精度，用于比较
const int MAXN = 1e5 + 5; // 最大数组大小

#ifdef DEBUG
#define dbg(x) cerr << #x << " = " << x << endl
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl
#else
#define dbg(x)
#define dbg2(x, y)
#endif

// 快速输入输出 - 加速cin/cout，竞赛必备
void fast_io()
{
    ios_base::sync_with_stdio(false); // 取消C++与C的同步
    cin.tie(nullptr);                 // 取消cin与cout的绑定
    cout.tie(nullptr);                // 取消cout的自动刷新
}

// 常用工具函数
template <typename T>
void print_vector(const vector<T> &v, const string &sep = " ")
{
    for (int i = 0; i < (int)v.size(); ++i) {
        if (i > 0)
            cout << sep;
        cout << v[i];
    }
    cout << "\n";
}

template <typename T>
T gcd(T a, T b)
{
    return b ? gcd(b, a % b) : a;
}

template <typename T>
T lcm(T a, T b)
{
    return a / gcd(a, b) * b;
}

template <typename T>
T power(T base, T exp, T mod = MOD)
{
    T result = 1;
    while (exp > 0) {
        if (exp % 2 == 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

// 数学工具
bool is_prime(ll n)
{
    if (n < 2)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    for (ll i = 3; i * i <= n; i += 2) {
        if (n % i == 0)
            return false;
    }
    return true;
}

vector<int> get_primes(int n)
{
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = (ll)i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

// 字符串工具
vector<string> split(const string &s, char delimiter)
{
    vector<string> tokens;
    stringstream ss(s);
    string token;
    while (getline(ss, token, delimiter)) {
        tokens.push_back(token);
    }
    return tokens;
}

string trim(const string &s)
{
    size_t start = s.find_first_not_of(" \t\n\r");
    if (start == string::npos)
        return "";
    size_t end = s.find_last_not_of(" \t\n\r");
    return s.substr(start, end - start + 1);
}

// 二分查找模板
template <typename T>
int lower_bound_custom(const vector<T> &arr, T target)
{
    int left = 0, right = sz(arr);
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

template <typename T>
int upper_bound_custom(const vector<T> &arr, T target)
{
    int left = 0, right = sz(arr);
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

// 快速输入输出工具 - 常用的输入输出操作
namespace QuickIO
{
// 读取一行整数，自动分割
vector<int> read_int_line()
{
    string line;
    getline(cin, line);
    istringstream iss(line);
    vector<int> result;
    int x;
    while (iss >> x) {
        result.push_back(x);
    }
    return result;
}

// 读取一行字符串，按分隔符分割
vector<string> read_string_line(char delimiter = ' ')
{
    string line;
    getline(cin, line);
    vector<string> result;
    stringstream ss(line);
    string item;

    if (delimiter == ' ') {
        while (ss >> item) {
            result.push_back(item);
        }
    } else {
        while (getline(ss, item, delimiter)) {
            result.push_back(item);
        }
    }
    return result;
}

// 读取矩阵（n行m列）
vector<vector<int>> read_matrix(int n, int m)
{
    vector<vector<int>> matrix(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    return matrix;
}

// 读取字符矩阵
vector<string> read_char_matrix(int n)
{
    vector<string> matrix(n);
    for (int i = 0; i < n; i++) {
        cin >> matrix[i];
    }
    return matrix;
}

// 输出矩阵
void print_matrix(const vector<vector<int>> &matrix, const string &sep = " ")
{
    for (const auto &row : matrix) {
        for (int i = 0; i < (int)row.size(); i++) {
            if (i > 0)
                cout << sep;
            cout << row[i];
        }
        cout << "\n";
    }
}

// 输出数组（一行）
template <typename T>
void print_array(const vector<T> &arr, const string &sep = " ")
{
    for (int i = 0; i < (int)arr.size(); i++) {
        if (i > 0)
            cout << sep;
        cout << arr[i];
    }
    cout << "\n";
}

// 输出数组（每个元素一行）
template <typename T>
void print_array_lines(const vector<T> &arr)
{
    for (const auto &item : arr) {
        cout << item << "\n";
    }
}

// 读取所有输入直到EOF
vector<string> read_all_lines()
{
    vector<string> lines;
    string line;
    while (getline(cin, line)) {
        lines.push_back(line);
    }
    return lines;
}

// 读取多组测试数据
template <typename Func>
void process_multiple_tests(Func solve)
{
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
} // namespace QuickIO
